//给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。 
//
// 请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。 
//
// 你可以假设 nums1 和 nums2 不会同时为空。 
//
// 
//
// 示例 1: 
//
// nums1 = [1, 3]
//nums2 = [2]
//
//则中位数是 2.0
// 
//
// 示例 2: 
//
// nums1 = [1, 2]
//nums2 = [3, 4]
//
//则中位数是 (2 + 3)/2 = 2.5
// 
// Related Topics 数组 二分查找 分治算法 
// 👍 3136 👎 0

package leetcode.editor.cn;

import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReference;

// Java4: 寻找两个正序数组的中位数
public class Q4MedianOfTwoSortedArrays {
    public static void main(String[] args) {
        Solution solution = new Q4MedianOfTwoSortedArrays().new Solution();
        System.out.println(solution.findMedianSortedArrays(new int[]{1,2}, new int[]{3, 4}));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            return my2(nums1, nums2);
        }

        private double my(int[] nums1, int[] nums2) {
            int total = nums1.length + nums2.length;
            TreeMap<Integer, Integer> map = new TreeMap<>();
            for (int i = 0; i < nums1.length; i++) {
                if (map.containsKey(nums1[i])) {
                    map.put(nums1[i], map.get(nums1[i])+1);
                } else {
                    map.put(nums1[i], 1);
                }
            }
            for (int i = 0; i < nums2.length; i++) {
                if (map.containsKey(nums2[i])) {
                    map.put(nums2[i], map.get(nums2[i])+1);
                } else {
                    map.put(nums2[i], 1);
                }
            }
            AtomicReference<Double> r = new AtomicReference<>((double) 0);
            AtomicInteger count = new AtomicInteger(0);
            Iterator<Map.Entry<Integer, Integer>> entries = map.entrySet().iterator();
            if (total%2==0) {
                int m1 = total/2;
                int m2 = m1 + 1;
                map.forEach((k, v) -> {
                    int a = count.get();
                    int b = count.addAndGet(v);
                    if (a < m1 && m1 <= b) {
                        r.set(r.get() + (Double.valueOf(k) / 2));
                    }
                    if (a < m2 && m2 <= b) {
                        r.set(r.get() + (Double.valueOf(k) / 2));
                    }
                });
            } else {
                int m = total/2 + 1;
                map.forEach((k, v) -> {
                    if (count.get() < m && m <= count.addAndGet(v)) {
                        r.set(Double.valueOf(k));
                    }
                });
            }
            return r.get();
        }

        private double my2(int[] nums1, int[] nums2) {
            int[] re = new int[(nums1.length+nums2.length)/2 + 1];

            int p1 = 0, p2 = 0;
            for (int i=0; i<re.length; i++) {
                int num1;
                if (p1 < nums1.length) {
                    num1 = nums1[p1];
                } else {
                    num1 = Integer.MAX_VALUE;
                }

                int num2;
                if (p2 < nums2.length) {
                    num2 = nums2[p2];
                } else {
                    num2 = Integer.MAX_VALUE;
                }

                if (num1 >= num2) {
                    re[i] = num2;
                    p2++;
                } else {
                    re[i] = num1;
                    p1++;
                }
            }

            if ((nums1.length+nums2.length)%2 == 0) {
                return ((double) re[re.length - 1] + (double) re[re.length - 2])/2;
            } else {
                return re[re.length - 1];
            }

        }

    }
    //leetcode submit region end(Prohibit modification and deletion)

}

